/**
 * @Author: lena
 * @Date: 2021/9/24 19:38
 * @Description: 单向链表
 * @Version: 1.0.0
 */

package data_structure

// 定义链表
type ListNode struct {
    val int
    next *ListNode
}

// 创建节点
func newListNode(val int) *ListNode {
    return &ListNode{
        val: val,
        next :nil,
    }
}

// 删除结点：返回head
func delete(head *ListNode,node *ListNode) (bool,*ListNode) {
    if head == nil {
        return false,nil
    }
    p2:=head
    if p2 == node {
        return true,head.next
    }
    p1:=p2
    p2=p2.next
    for p2!=nil {
        // 找到了要删除的结点
        if p2 == node {
            // 删除结点
            p1.next=p2.next
            // 返回
            return true,head
        }
        p1=p2
        p2=p2.next
    }
    return false,head
}

// 增加节点：尾部
func add(head *ListNode,node *ListNode) (bool,*ListNode) {
    if head == nil {
        return false,nil
    }
    p := head
    for p.next!=nil {
        p=p.next
    }
    p.next=node
    return true,head
}

// 修改节点：用新节点替换旧节点
func updata(head *ListNode,node *ListNode,new *ListNode) (bool,*ListNode) {
    if head == nil {
        return false,nil
    }
    // 头结点就是要修改的结点
    if head == node {
        new.next=head.next
        return true,new
    }
    p:=head.next
    p1:=head
    for p != nil {
        // p指向结点是要替换的结点
        if p == node {
            // 使用新节点替换原来的节点
            p1.next=new
            new.next=p.next
            return true,head
        }
        p1=p
        p=p.next
    }
    return false,head
}

// 查询某一值的节点：前提要求链表内值不重复
func findOne(head *ListNode,val int) (bool,*ListNode) {
    if head == nil {
        return false,nil
    }
    p:=head
    for p!=nil {
        if p.val == val {
            return true,p
        }
        p=p.next
    }
    return false,nil
}

// 遍历节点：以数组形式返回
func list(head *ListNode) []int {
    if head == nil {
        return []int{}
    }
    res:=make([]int,10) // TODO：怎么动态调整数组大小？
    p := head
    for i:=0;p != nil;i++ {
        res[i]=p.val
        p=p.next
    }
    return res
}

// 查找某个节点的前驱节点
func findPre(head *ListNode,node *ListNode) (bool,*ListNode) {
    if head == nil {
        return false,nil
    }
    p1:=head
    p2:=head.next
    for p2 != nil {
        if p2 == node {
            return true,p1
        }
        p1=p2
        p2=p2.next
    }
    return false,nil
}

// 计算链表长度
func len(head *ListNode) (res int) {
    p:=head
    for p != nil {
        res++
        p=p.next
    }
    return res
}